package Leetcode.数组字符串;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/5/15 11:53
 * @Description:
 * 完成所有任务的最少时间
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。
 *
 * 当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。
 *
 * 请你返回完成所有任务的情况下，电脑最少需要运行多少秒。
 *
 *
 *
 * 示例 1：
 *
 * 输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
 * 输出：2
 * 解释：
 * - 第一个任务在闭区间 [2, 2] 运行。
 * - 第二个任务在闭区间 [5, 5] 运行。
 * - 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
 * 电脑总共运行 2 个整数时间点。
 * 示例 2：
 *
 * 输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
 * 输出：4
 * 解释：
 * - 第一个任务在闭区间 [2, 3] 运行
 * - 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
 * - 第三个任务在闭区间 [5, 6] 运行。
 * 电脑总共运行 4 个整数时间点。
 *
 *
 * 提示：
 *
 * 1 <= tasks.length <= 2000
 * tasks[i].length == 3
 * 1 <= starti, endi <= 2000
 * 1 <= durationi <= endi - starti + 1
 */

public class findMinimumTime {
    public int findMinimumTime(int[][] tasks) {
        int n = tasks.length; // 任务数
        // 根据任务的结束时间对任务进行排序
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        int[] run = new int[tasks[n - 1][1] + 1]; // 创建一个长度为最大结束时间加一的数组，用来记录每个时间点是否有任务在运行
        int res = 0; // 结果变量，记录最小的总时间
        for (int i = 0; i < n; i++) {
            int start = tasks[i][0], end = tasks[i][1], duration = tasks[i][2];
            // 遍历任务的运行区间，减少剩余运行时间
            for (int j = start; j <= end; j++) {
                duration -= run[j];
            }
            res += Math.max(duration, 0); // 更新结果，取剩余运行时间的最大值或0
            for (int j = end; j >= 0 && duration > 0; j--) {
                // 如果当前时间点没有任务在运行，并且任务还有剩余运行时间，则减少一个时间点的运行时间
                if (run[j] == 0) {
                    duration--;
                    run[j] = 1; // 标记当前时间点有任务在运行
                }
            }
        }
        return res; // 返回最小的总时间
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        findMinimumTime scheduler = new findMinimumTime();
        int[][] tasks = {{0, 3, 5}, {1, 3, 4}, {2, 4, 1}};
        int minTime = scheduler.findMinimumTime(tasks);
        System.out.println("Minimum time required: " + minTime);
    }
}
